//
// Created by Administrator on 2021/6/10.
//

//给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int change(int amount, vector<int> &coins) {
        if (amount == 0) return 1;
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        /**
         * 为了避免重复,外层遍历硬币,内层遍历金额
         */
        for (auto &val : coins) { // 遍历硬币面额
            for (int i = 1; i <= amount; ++i) { // 遍历目标面额
                if (val <= i) {
                    dp[i] += dp[i - val];
                }
            }
        }
        return dp.back();
    }
};

int main() {
    vector<int> coins{1, 2, 5};
    Solution sol;
    cout << sol.change(5, coins) << endl;
    return 0;
}